package com.wfm.leetcode.editor.cn;
public class PTwo79完全平方数{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];

        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j*j <= i ; j++) {
                min=Math.min(dp[i-j*j],min);
            }
            dp[i]=min+1;
        }
        return dp[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PTwo79完全平方数().new Solution();
    }
}